package com.itheima.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 滑动窗口最大值 - 单调递减队列
 */
public class SlidingWindowMaximumLeetcode239 {

    // 每次向单调递减队列加入元素，对头元素即为滑动窗口最大值
    public static int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue queue = new MonotonicQueue();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 检查队列头部元素，超过滑动窗口范围要移除
            if (k <= i && nums[i - k] == queue.peek()) { // 元素超出 滑动窗口范围 移除判断
                /*
                     移除的是上一次的滑动窗口和队列首位，因为是单调队列，超出范围的那个元素必定是当时3个当中第一个进入的，
                     因为相对来说是第一个进的，一直都在队列内，那一定是队列第一位，所以nums[i - k] == queue.peek()
                     滑动窗口的位置                最大值
                    ---------------               -----
                    [1  3  -1] -3  5  3  6  7       3
                     1 [3  -1  -3] 5  3  6  7       3
                     1  3 [-1  -3  5] 3  6  7       5
                     1  3  -1 [-3  5  3] 6  7       5
                     1  3  -1  -3 [5  3  6] 7       6
                     1  3  -1  -3  5 [3  6  7]      7
                 */
                queue.poll();
            }
            int num = nums[i];
            queue.offer(num);
            if (k - 1 <= i) {
//                System.out.println(queue.peek());
                list.add(queue.peek());
            }
        }
        return list.stream().mapToInt(integer -> integer.intValue()).toArray();
    }

    public static void main(String[] args) {
//        int[] candidates = {1, 3, -1, -3, 5, 3, 6, 7}; // [3, 3, 5, 5, 6, 7]
        int[] candidates = {1, 3, -1, -3, -4, 5, 3, 6, 7}; // 错误答案 [3, 3, 3, 5, 5, 6, 7]
        System.out.println(Arrays.toString(maxSlidingWindow(candidates, 3)));
    }
}
